package com.lcm.algorithm.datatest.dp;

/**
 * @description:
 * @author: lcm
 * @create: 2020-04-29 09:30
 **/

public class UniquePath {

    public static void main(String[] args){
        UniquePath path=new UniquePath();
        System.out.println(path.uniquePaths(7,3));
        System.out.println(path.uniquePathsWithObstacles(new int[][]{{0,0,0},{0,1,0},{0,0,0}}));
    }

    /**
     * 1.暴力递归
     * 2.记忆化搜索优化
     * 3.动态规划优化
     */
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m+1][n+1];
        return help(m,n,dp);
    }

    int help(int i,int j,int[][] dp){
        if(i<=0||j<=0) return 0;
        if(i==1&&j==1) return 1;
        if(dp[i][j]!=0){
            return dp[i][j];
        }
        dp[i][j]=help(i-1,j,dp)+help(i,j-1,dp);
        return dp[i][j];
    }

    /**
     * 63. 不同路径 II
     *
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
     *
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
     *
     * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
     *
     * 网格中的障碍物和空位置分别用 1 和 0 来表示。
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int[][] dp=new int[obstacleGrid.length+1][obstacleGrid[0].length+1];
        dp[1][1]=1;
        return helpWithObstacles(obstacleGrid.length,obstacleGrid[0].length,dp,obstacleGrid);
    }
    int helpWithObstacles(int i,int j,int[][] dp,int[][] obstacleGrid){
        if(i<=0||j<=0||obstacleGrid[i-1][j-1]==1) return 0;
        if(dp[i][j]!=0){
            return dp[i][j];
        }
        dp[i][j]=helpWithObstacles(i-1,j,dp,obstacleGrid)+helpWithObstacles(i,j-1,dp,obstacleGrid);
        return dp[i][j];
    }

}
